package com.interview.javabasic.Algorithm;/*
@李子宁
Happy,happy everyday!
冲鸭！
*/

import java.util.Arrays;

public class PrimAlgorithm {
    public static void main(String[] args) {
        char[] data = new char[]{'A','B','C','D','E','F','G'};
        int verxs = data.length;
        //邻接矩阵的关系
        int[][] weight = new int[][]{
                {10000,5,7,10000,10000,10000,2},
                {5,10000,10000,9,1000,10000,3},
                {7,10000,10000,10000,8,10000,10000},
                {10000,9,10000,10000,10000,4,10000},
                {10000,10000,8,10000,10000,5,4},
                {10000,10000,10000,4,5,10000,6},
                {2,3,10000,10000,4,6,10000}
        };
        //创建MGraph对象
        MGraph  mGraph = new MGraph(verxs);
        //创建一个
        MinTree minTree = new MinTree();
        minTree.creatGraph(mGraph,verxs,data,weight);
        minTree.showGraph(mGraph);
        minTree.prim(mGraph,1);

    }
}

//创建最小生成树
class MinTree{
    public void creatGraph(MGraph graph,int vertext,char[] data,int[][] weight){
        int i,j;
        for ( i = 0; i < vertext; i++) {
            graph.data[i] = data[i];
            for (j = 0;j<vertext;j++){
                graph.weight[i][j] = weight[i][j];
            }
        }
    }
    
    //显示图
    public void showGraph(MGraph graph){
        for (int[] ints : graph.weight) {
            System.out.println(Arrays.toString(ints));
        }
    }

    //编写prim算法
    public void prim(MGraph graph,int v){
        //标记节点是否被访问过
        int[] visited = new int[graph.vertext];
        //把当前节点标记为已访问
        visited[v]=1;
        //h1和h2记录两个顶点的下标
        int h1 = -1;
        int h2 = -1;
        int minWeight = 10000;//初始化为不可达位置，后面在遍历过程中会被改变
        //确定每一次生成的子图，和哪个节点的距离最近。
        for (int k = 1; k < graph.vertext; k++) {
        for (int i = 0; i < graph.vertext; i++) {//因为有vertex多的顶点，算法结束后。会有顶点数减一条边
            for (int j = 0; j < graph.vertext; j++) {
                if (visited[i]==1 && visited[j]==0 && graph.weight[i][j]<minWeight){
                    minWeight = graph.weight[i][j];
                    h1 = i;
                    h2 = j;
                }
            }
        }
            System.out.println("边<"+graph.data[h1]+","+graph.data[h2]+">权值： "+minWeight);
        visited[h2] = 1;
        //重新设置为10000；
        minWeight = 10000;
        }
    }
}

class MGraph{
    int vertext;//图中节点的个数
    char[] data;//存放节点数据
    int[][] weight;//存放边

    public MGraph(int vertext){
        this.vertext = vertext;
        data = new char[vertext];
        weight = new int[vertext][vertext];
    }
}


